package euler.p001_050;

import java.math.BigDecimal;

import euler.MainEuler;

public class Euler026 extends MainEuler {

    /*
        A unit fraction contains 1 in the numerator.
        The decimal representation of the unit fractions
        with denominators 2 to 10 are given:

            1/2 =   0.5
            1/3 =   0.(3)
            1/4 =   0.25
            1/5 =   0.2
            1/6 =   0.1(6)
            1/7 =   0.(142857)
            1/8 =   0.125
            1/9 =   0.(1)
            1/10    =   0.1

        Where 0.1(6) means 0.166666..., and has a 1-digit recurring
        cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

        Find the value of d < 1000 for which 1/d contains the longest
        recurring cycle in its decimal fraction part.

     */
    public String resolve(int limite) {

        int longest = 0;
        int bestD = 0;

        for (int i = 2; i < limite; i++) {
            BigDecimal bd = BigDecimal.ONE.divide(BigDecimal.valueOf(i), 2*i+1, BigDecimal.ROUND_DOWN);
            String cycle = findCycle(bd.toPlainString().substring(2));

            if (longest < cycle.length()) {
                longest = cycle.length();
                bestD = i;
            }
        }

        return String.valueOf(bestD);
    }

    private String findCycle(String decimal) {
        int pos = 0;
        int offset = 0;

        while (decimal.length() > 0) {
            if (decimal.length() == 1) {
                return null;
            }

            int index = decimal.substring(pos+offset+1).indexOf(decimal.charAt(pos));

            while (index == -1 && (pos+offset+1) < decimal.length()) {
                index = decimal.substring(pos+offset+1).indexOf(decimal.charAt(pos));
                pos++;
            }

            if ((pos+offset+1) == decimal.length()) {
                decimal = decimal.substring(1);
                pos = 0;
                offset = 0;
            } else {
                String target = decimal.substring(pos,index+pos+1+offset);

                boolean correct = decimal.length() > 2*target.length();
                for (int i = target.length() + 1; correct && i < decimal.length(); i++) {
                    correct = decimal.charAt(i) == target.charAt(i%target.length());
                }

                if (correct) {
                    return target;
                } else if (2*offset <= decimal.length()) {
                    offset++;
                } else {
                    decimal = decimal.substring(1);
                    pos = 0;
                    offset = 0;
                }
            }
        }

        return decimal;
    }

}
